package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _229_MajorityElementIi {
    public static void main(String[] args) {
        Solution solution = new _229_MajorityElementIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> majorityElement(int[] nums) {
            int n = nums.length;
            List<Integer> res = new ArrayList<>();
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() > n / 3) {
                    res.add(entry.getKey());
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}